public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {7, 5, 11, 2, 4, 6, 9, 1, 8, 3};
        System.out.print("排序前:  ");
        print(arr);

        insertSort(arr);
        System.out.print("排序后:  ");
        print(arr);
    }

    public static void insertSort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        for (int i = 0; i < arr.length - 1; i++) {
            int value = arr[i + 1];
            int j = i;
            for (; j >= 0 && arr[j] > value; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = value;
//         System.out.print("第 "+ (i+1) + " 趟: ");
//         print(arr);
        }
    }

    public static void print(int[] arr) {
        if (arr == null) return;
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}